package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * WARNING, hard
 * 拆分子问题, 使用最后扎的那个气球进行拆分
 * 最后扎的相当于一个锚点!
 * - 确定好最后扎的, 两个字序列的两侧的东西是固定的.
 * - f(i,j)表示左右有气球的时候(边界视为值为1的球), 扎爆i到j的得分
 * - nums长5, f(2,3)则表示两边都在的情况下扎爆2,3得分
 * <p>
 * 类似 快排??
 * <p>
 * 类似 一个无序数组, 找第k大的数
 *
 * @author tzp
 * @since 2020/9/17
 */
public class LC312 implements DynamicProblem {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[][] state = new int[nums.length][nums.length];
        for (int end = 0; end < nums.length; end++) {
            for (int start = end; start >= 0; start--) {
                int leftFence = start - 1 >= 0 ? nums[start - 1] : 1;
                int rightFence = end + 1 < nums.length ? nums[end + 1] : 1;
                if (start == end) {
                    state[start][end] = leftFence * nums[start] * rightFence;
                } else {
                    int max = Integer.MIN_VALUE;
                    for (int lastCha = start; lastCha <= end; lastCha++) {
                        int currentPlan;
                        if (lastCha == start) {
                            currentPlan = leftFence * nums[lastCha] * rightFence + state[lastCha + 1][end];
                        } else if (lastCha == end) {
                            currentPlan = leftFence * nums[lastCha] * rightFence + state[start][lastCha - 1];
                        } else {
                            currentPlan = leftFence * nums[lastCha] * rightFence
                                    + state[start][lastCha - 1]
                                    + state[lastCha + 1][end];
                        }
                        max = Math.max(max, currentPlan);
                    }
                    state[start][end] = max;
                }
            }
        }
        return state[0][nums.length - 1];
    }

    public static void main(String[] args) {
//        System.out.println(new LC312().maxCoins(new int[]{3, 1, 5}));
        System.out.println(new LC312().maxCoins(new int[]{3, 1, 5, 8}));
    }
}
